package com.ycy.leetcode.dongtaiguihua;

import com.ycy.Utils;
import org.junit.Test;

import java.util.Arrays;

/**
 *  打家劫舍
 */
public class DaJiaJieShe {

  /*
  打家劫舍问题
  相邻的房子不能偷，求能盗取的最大金额
   */
  @Test
  public void test() {
    int[] ints = Utils.RandomArr(5);
    this.arr = ints;
//    this.arr = new int[]{13,35,47,34};
    System.out.println(Arrays.toString(arr));
    int money = MaxMoney(this.arr.length - 1);
    System.out.println(money);
  }

  int[] arr;

  /**
   * 在当前位置，所能得到的最大金额
   */
  public int MaxMoney(int i) {
    if (i == 0) return this.arr[0];
    if (i == 1) return max(this.arr[0], this.arr[1]);
    return max(MaxMoney(i - 1), MaxMoney(i - 2) + this.arr[i]);
  }

  public int max(int a, int b) {
    return Math.max(a, b);
  }

}
